package afi.ch1;

/**
 * @author Pavel Belevich
 *         Date: 6/21/12
 *         Time: 7:43 PM
 */
public class BinarySearch {

    static int mySearch(int[] A, int K) {
        int start = 0;
        int end = A.length - 1;
        int m = 0;
        do {
            m = (start + end) / 2;
            if (A[m] < K) {
                start = m;
            } else if (A[m] > K) {
                end = m;
            } else {
                return m;
            }
        } while (true);
    }

    static int mySearch2(int[] A, int K) {
        int start = 0;
        int end = A.length - 1;
        int m = 0;
        while (start <= end) {
            m = (start + end) / 2;
            if (A[m] < K) {
                start = m + 1;
            } else if (A[m] > K) {
                end = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    static int search(int[] A, int K) {
        int l = 0;
        int u = A.length - 1;
        int m;
        while (l <= u) {
            m = (l+u) / 2;
            if (A[m] < K) {
                l = m + 1;
            } else if (A[m] == K) {
                return m;
            } else {
                u = m-1;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] A = { 1, 4, 5, 6, 9,10,12,17,20,33};
        for (int i : A) {
            System.out.println(mySearch2(A, i));
        }
        System.out.println("============================================");
        int[] B = {};
        System.out.println(mySearch2(B, 1));
        System.out.println("============================================");
        int[] C = {10};
        System.out.println(mySearch2(C, 5));
        System.out.println(mySearch2(C, 10));
        System.out.println(mySearch2(C, 15));
        System.out.println("============================================");
        int[] D = {10, 15};
        System.out.println(mySearch2(D, 5));
        System.out.println(mySearch2(D, 10));
        System.out.println(mySearch2(D, 15));
        System.out.println(mySearch2(D, 20));
    }
    
}
